1. Field of the Invention
The present invention generally relates to a digital communication system, and in particular to a rate matching method for producing an output string of m symbols from an input string of n (nxe2x88x92m) symbols
2. Description of the Related Art
In the field of digital communication systems, there have been proposed several rate matching methods for obtaining output sequence of m symbols from input sequence of n symbols. In the case of n greater than m, the first (nxe2x88x92m) symbols of the input symbol string are deleted to produce the output string of the remaining m symbols. In the case of n less than m, after repeating a top input symbol (mxe2x88x92n+1) times, m symbols following the top input symbol are output to produce the output string of m symbol.
In the case of the symbol sequence encoded with a convolution code, it is known that the original information can be reproduced correctly, even if the symbol sequence has been partly deleted, by inserting dummy symbols into the imperfect symbol sequence at the positions corresponding to the deleted symbols when decoded. Such error-correction decoding is allowed by the coding gain achieved by a convolution code.
In general, many decoding systems are susceptible to an error burst, and when a number of symbols have been consecutively deleted as mentioned above, they cannot fully exhibit the error correction capability.
On the other hand, in the case where the same symbol is consecutively repeated, the energy of the repeated symbol becomes large in equivalent by using the energy of the repeated symbol effectively. This may allow error rate to be effectively reduced around the repeated symbol. In the case of the convolution code, however, the reduction in error rate for symbols more than the constraint length away from that symbol cannot be expected at all.
To solve these problems to some extent, there has been proposed a rate matching method conforming to IMT-2000 scheme, which is now under standardization by ARIB (Association of Radio Industries and Businesses). The details of this method are described in xe2x80x9cVolume 3, Specification of Air-Interface for the 3G Mobile System Version 0.5xe2x80x9d. Hereafter, this specification will be described briefly.
Assuming that an input symbol sequence is denoted by S0 the number of input symbols thereof by n, and the number of output, symbol of an output symbol sequence by m, a symbol-deletion rate matching method (n greater than m) is performed according to the following algorithm:
(a) j=0, x=n, and y=nxe2x88x92m;
(b) go to step (c) when y is equal to greater than 1, and exit otherwise with the current symbol sequence S being an output sequence;
(c) set z to a minimum integer which is not smaller than x/y;
(d) set k to a maximum integer which is not greater than x/z;
(e) delete a symbol every z symbols from the symbol sequence Sj and the resultant symbol sequence is denoted by Sj,1;
(f) x=xxe2x88x92k, y=yxe2x88x92k, and j=j+1; and
(g) go back to step (b).
A symbol-repetition rate matching method (n less than m) is performed according to tho following algorithm:
(A) j=0;
(B) go to step (C) when 2n is smaller than m, and go to step (F) otherwise;
(C) repeat all symbols of Sj one time and the resultant is denoted by Sj+1;
(D) n=2n, and j=j+1,
(E) go back to step (B);
(F) x=n, and y=mxe2x88x92n;
(G) go to step (H) when y exceeds 1, and go to step (M) otherwise;
(H) set z to a minimum integer which is not smaller than x/y;
(I) set k to a maximum integer which Is not greater than x/z;
(J) repeat Sj every z symbols unless it has been already repeated, and the resultant symbol sequence is denoted by Sj+1;
(K) x=xxe2x88x92k, y=yxe2x88x92k, and j=j+1;
(L) go back to step (J); and
(M) when y=1, repeat only the first symbol of Sj and the resultant symbol sequence is denoted by Sj+1 before exit, and when y in not equal to 1, exit with the current symbol sequence S being an output sequence.
FIG. 15 shows concrete operations of a conventional symbol-deletion rate matching method conforming to the IMT-2000 scheme. Here, it is assumed that the number of input symbols is 128 (nxe2x88x92128) and the number of output symbols is 100 (mxe2x88x92100).
As shown in FIG. 15A, symbol sequence S0 of n=128 is inputted. According to the symbol-deletion rate matching algorithm, the steps (a)-(e) provide x=128, y=28, z=5, and k=25, resulting in a symbol sequence S1 as shown in FIG. 15B.
This symbol sequence S1 is obtained by deleting S0 every five symbols.
When the steps (a)-(e) are performed for a second time, x =xxe2x88x92k=103, y=yxe2x88x92k=3, z=35, and k=2 are obtained. Therefore the symbol sequence S1 is deleted every 35 symbols, resulting in a symbol sequence S2 as shown in FIG. 15C.
When the steps (a)-(e) are performed for a third time, X=101, y=1, z=101, and k=1 are obtained. Therefore, the symbol sequence S2 is deleted every 101 symbols that is only the last symbol is deleted, resulting in the final symbol sequence S3 as shown in FIG. 15D. Therefore, in this example the input symbol sequence of 128 symbols is converted into the output symbol sequence of 100 symbols by three-time symbol deletion operation.
It will be understood from the example shown in FIGS. 15A-15D that each deleting operation (steps (a)-(e)) provides the maximum interval between deleted symbols, resulting in optimum deletion processing, but the optimum deletion processing is not always performed between deleting operations because the relation between the current and the previous deleting operations is not sufficiently taken into account.
More specifically, since the interval between deleted symbols have been maximized in the previous deleting operation, the current deleting operation can provide a symbol-deletion interval equal to or smaller than that of the previous deleting operation (in most cases, a half or less the symbol-deletion interval achieved by the previous deleting operation).
As shown in FIG. 15B, the 45th symbol of the symbol sequence S1 is deleted. Subsequently, the 43rd symbol is deleted as shown in FIG. 15C. Similarly, the 85th and 87th symbols are deleted. In this case, the distance between deleted symbols is only two symbols.
As described above, according to the conventional algorithm, symbol deletion may be performed at a plurality of consecutive positions depending on the relation between the numbers of input and output symbols. There is a high possibility that the symbol sequence deleted like this causes problems when demodulated and decoded.
Similarly, in the case of symbol-repetition rate matching, the positions of repeated symbols may be distributed unevenly, producing a symbol region susceptible to error and a symbol region resistant to error.
An object of the present invention is to provide a rate matching method that can achieve more reliable data communication.
According to the present invention, a rate matching method produces m output symbols from n (nxe2x89xa0m) input symbols by a selected one of symbol deletion and symbol repetition depending on a comparison result of n and m, where n and m are an integer greater than 0. The method comprises the step of maximizing a smallest interval between symbols subjected to the selected one of the symbol deletion and the symbol repetition and the step of maximizing a sum total of intervals of symbols subjected to the selected one of the symbol deletion and the symbol repetition.
An interval of symbols subjected to the selected one of the symbol deletion and the symbol repetition may be one of k and kxe2x88x921, where k is an integer greater than 0.
According to the present invention, a rate matching method for inputting a first symbol string S(k) of n symbols and outputting a second symbol string d(j) of m (nxe2x89xa0m) symbols in a digital communication system, where n and m are an integer greater than 0, k is an integer ranging from 0 to nxe2x88x921, and j is an integer ranging from 0 to mxe2x88x921. comprises the steps of: a) setting a difference (D) between n and m; b) setting Q=n/D; c) sequentially dividing the first symbol string S(k) to produce D symbol strings each consisting of either Q symbols or (Q+1) symbols: d) selecting a single symbol located at a predetermined position for each of the D symbol strings; and e) producing the second symbol string d(j) by performing one of deletion and repetition of the single symbol for each of the D symbol strings depending on a comparison result of n and m.
The first symbol string S(k) is preferably included in encoded symbol sequence produced with an error-correction code such as a convolution code.
Preferably, the second symbol string d(j) is interleaved and then transmitted and the first symbol string S(k) is produced by deinterleaving a received symbol string.
Further preferably, the step (c) includes the step of determining a position (R,C) of each element of an arrangement to sequentially arrange the first symbol string S(k), wherein C and R are determined as follows:
C=INT(kxc3x97D/n);
and
R=INT(kxe2x88x92Cxc3x97n/D),
where INT(x) is a function of obtaining an integer part of x.
As described above according to the present invention, the narrowest interval and the widest interval between deleted or repeated symbols are almost the same. In other words, the narrowest interval is maximized, resulting in the maximized sum total of intervals of deleted or repeated symbols. In addition, the positions of deleted or repeated symbols are spread out uniformly over the input symbol string. Therefore, reliable and stable digital communication can be achieved.